Grokking Microsoft Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
Microsoft Easy Problems
Buddy Strings (easy)
Solution: Buddy Strings
Can Place Flowers (easy)
Solution: Can Place Flowers
Reverse a LinkedList (easy)
Solution: Reverse a LinkedList
Maximum Number of Balloons (easy)
Solution: Maximum Number of Balloons
Binary Tree Path Sum (easy)
Solution: Binary Tree Path Sum
Pair with Target Sum (easy)
Solution: Pair with Target Sum
Buy Two Chocolates (easy)
Solution: Buy Two Chocolates
Root Equals Sum of Children (easy)
Solution: Root Equals Sum of Children
Excel Sheet Column Title (easy)
Solution: Excel Sheet Column Title
Merge Strings Alternately (easy)
Solution: Merge Strings Alternately
Min Cost Climbing Stairs (easy)
Solution: Min Cost Climbing Stairs
Plus One (easy)
Solution: Plus One
Intersection of Two Arrays (easy)
Solution: Intersection of Two Arrays
Find the Index of the First Occurrence in a String (easy)
Solution: Find the Index of the First Occurrence in a String
Merge Two Sorted Lists (easy)
Solution: Merge Two Sorted Lists
Microsoft Medium Problems
Nth Digit (medium)
Solution: Nth Digit
Restore IP Addresses (medium)
Solution: Restore IP Addresses
Find Original Array From Doubled Array (medium)
Solution: Find Original Array From Doubled Array
Reverse Words in a String II (medium)
Solution: Reverse Words in a String II
Longest Arithmetic Subsequence (medium)
Solution: Longest Arithmetic Subsequence
Matchsticks to Square (medium)
Solution: Matchsticks to Square
Score of Parentheses (medium)
Solution: Score of Parentheses
Maximum Length of a Concatenated String with Unique Characters (medium)
Solution: Maximum Length of a Concatenated String with Unique Characters
Inorder Successor in BST (medium)
Solution: Inorder Successor in BST
Distribute Coins in Binary Tree (medium)
Solution: Distribute Coins in Binary Tree
Spiral Matrix (medium)
Solution: Spiral Matrix
Delete Node in a BST (medium)
Solution: Delete Node in a BST
Sum of Subarray Minimums (medium)
Solution: Sum of Subarray Minimums
Rotate Image (medium)
Solution: Rotate Image
Combinations (medium)
Solution: Combinations
Maximum Level Sum of a Binary Tree (medium)
Solution: Maximum Level Sum of a Binary Tree
Multiply Strings (medium)
Solution: Multiply Strings
Best Time to Buy and Sell Stock II (medium)
Solution: Best Time to Buy and Sell Stock II
Largest Palindromic Number (medium)
Solution: Largest Palindromic Number
Remove Duplicate Letters (medium)
Solution: Remove Duplicate Letters
Next Permutation (medium)
Solution: Next Permutation
132 Pattern (medium)
Solution: 132 Pattern
Valid Sudoku (medium)
Solution: Valid Sudoku
Number of Islands (medium)
Solution: Number of Islands
Buildings With an Ocean View (medium)
Solution: Buildings With an Ocean View
Microsoft Hard Problems
Regular Expression Matching (hard)
Solution: Regular Expression Matching
First Missing Positive (hard)
Solution: First Missing Positive
Largest Rectangle in Histogram (hard)
Solution: Largest Rectangle in Histogram
Sliding Window Maximum (hard)
Solution: Sliding Window Maximum
Count Unique Characters of All Substrings of a Given String (hard)
Solution: Count Unique Characters of All Substrings of a Given String
Word Ladder (hard)
Solution: Word Ladder
Word Ladder II (hard)
Solution: Word Ladder II
Number of Flowers in Full Bloom (hard)
Solution: Number of Flowers in Full Bloom
Median of Two Sorted Arrays (hard)
Solution: Median of Two Sorted Arrays
Longest Valid Parentheses (hard)
Solution: Longest Valid Parentheses
Solution: Word Ladder II

Problem Statement

A transformation sequence is a sequence that starts from the word beginWord, ends with endWord, and contains a word from the given dictionary wordList in the middle i.e. a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:

  • Each adjacent pair of words differs by a single letter.
  • Each si for 1 <= i <= k is in wordList. sk == endWord
  • The beginWord does not need to be in wordList.

Given two strings, beginWord and endWord, and a wordList, return all the shortest transformation sequences, or an empty list if no such sequence exists. Each sequence should be in the form of [beginWord, s1, s2, ..., sk].

Examples

  1. Example 1

    • Input: start = "cat", end = "dog", wordList = ["dat", "dot", "dog"]
    • Expected Output: [["cat", "dat", "dot", "dog"]]
    • Justification: The sequence "cat" -> "dat" -> "dot" -> "dog" changes one letter at a time, and each word exists in the wordList. It's the shortest path from "cat" to "dog".
  2. Example 2

    • Input: start = "bit", end = "fog", wordList = ["but", "put", "big", "pot", "pog", "dog"]
    • Expected Output: []
    • Justification: Although there are words in the list that are one letter away from "bit", there's no sequence that successfully transforms "bit" to "fog" through words in the wordList.
  3. Example 3

    • Input: start = "hot", end = "cog", wordList = ["dot", "dog", "lot", "log", "cog"]
    • Expected Output: [["hot", "dot", "dog", "cog"], ["hot", "lot", "log", "cog"]]
    • Justification: This example shows two possible shortest transformation sequences from "hot" to "cog". Each sequence involves changing one letter at a time with all intermediate words existing in the given wordList.

Solution

To solve this problem, we'll use a breadth-first search (BFS) strategy to explore all possible word transformations, ensuring that we only proceed through valid words in the given dictionary. This approach is effective because it naturally finds the shortest paths first, avoiding unnecessary exploration of longer paths. We'll maintain a queue to keep track of the paths explored at each step and a set to record words that have already been visited to prevent revisiting them. By exploring words in layers and tracking the path taken to reach each word, we can ensure that once we reach the target word, all paths found are of the shortest possible length.

The key to efficiency in this approach is to dynamically generate possible word transformations by changing each letter of the current word to every letter from 'a' to 'z' and checking if the new word exists in the wordList. This method minimizes the number of unnecessary comparisons and quickly identifies viable paths. The use of a queue facilitates the BFS approach, and tracking visited words ensures we don't cycle through the same words repeatedly.

Step-by-step Algorithm

  1. Initialize Data Structures:

    • Word List: Convert the input word list into a set for efficient lookup.
    • Adjacency List: Create a map (or dictionary) to store the adjacency list, representing the graph of word transformations.
    • Distances: Create a map (or dictionary) to store the distance (number of transformations) from the start word to each word encountered during BFS.
  2. Check for End Word:

    • Check if the endWord exists in the wordList. If it does not, return empty list immediately since transformation is impossible without the endWord being in the list.
  3. Breadth-First Search (BFS):

    • Initialize a queue and add the start word to it. Set the distance for the start word to 0 in the distances map.
    • While the queue is not empty, process each word in the queue:
      • For the current word, generate all possible one-letter transformations.
      • For each transformation that is in the word list and has not been visited (i.e., not in the distances map):
        • Add it to the queue.
        • Set its distance as one more than the current word's distance.
        • Add the transformation as an adjacent word to the current word in the adjacency list.
    • Continue until the queue is empty or the end word is reached.
  4. Depth-First Search (DFS):

    • Start DFS from the start word with the current path containing only the start word.
    • For each word in the current path, explore all adjacent words (transformations) as per the adjacency list.
    • If an adjacent word is the next step towards the end (i.e., its distance is one more than the current word's distance), add it to the current path and continue DFS with this new word.
    • If the end word is reached, add the current path to the results.
    • Backtrack by removing the last word from the current path before returning to explore another branch.
  5. Returning Results:

    • After completing DFS, return all found paths that transform the start word to the end word through valid transformations in the word list.

Algorithm Walkthrough

Let's consider the input: start = "hot", end = "cog", wordList = ["dot", "dog", "lot", "log", "cog"]

  1. Initialization:

    • The word list is converted to a set for efficient lookups: {"dot", "dog", "lot", "log", "cog"}.
    • Adjacency list and distances are initialized as empty structures.
  2. BFS to Build Adjacency List and Distances:

    • Enqueue "hot" and set its distance to 0.
    • Dequeue "hot" and explore its neighbors (one-letter transformations present in the word list): "dot" and "lot".
    • Enqueue "dot" and "lot", setting their distances to 1. Update the adjacency list to show "hot" is connected to "dot" and "lot".
    • Continue BFS:
      • Dequeue "dot", find its neighbors: "dog". Enqueue "dog", set its distance to 2, and update the adjacency list.
      • Dequeue "lot", find its neighbors: "log". Enqueue "log", set its distance to 2, and update the adjacency list.
      • Dequeue "dog", find its neighbor: "cog". Enqueue "cog", set its distance to 3, and update the adjacency list.
      • Dequeue "log", which also leads to "cog", but as "cog" is already visited with the same distance, just update the adjacency list.
    • BFS ends when the queue is empty.
  3. DFS to Find All Paths:

    • Start DFS with "hot". The current path is ["hot"].
    • Explore paths from "hot" to its neighbors: "dot" and "lot".
      • For "dot", the path becomes ["hot", "dot"]. Continue DFS from "dot":
        • Only neighbor "dog" has the correct distance. Path becomes ["hot", "dot", "dog"].
        • From "dog", go to "cog". Path is ["hot", "dot", "dog", "cog"]. This is a valid path, add it to results.
      • Backtrack to ["hot"] and then to ["hot", "lot"].
        • From "lot", go to "log". Path becomes ["hot", "lot", "log"].
        • From "log", go to "cog". Path is ["hot", "lot", "log", "cog"]. This is another valid path, add it to results.
    • DFS completes once all paths from "hot" have been explored.
  4. Results:

    • The algorithm finds two shortest transformation sequences: ["hot", "dot", "dog", "cog"] and ["hot", "lot", "log", "cog"].

Code

Java
Saved to Cloud

. . . .

Complexity Analysis

Time Complexity:

  • BFS Complexity: The BFS part of the algorithm involves traversing each word in the wordList (N words) and for each word, generating all possible one-letter transformations (at most transformations, where K is the length of the word). This results in a time complexity of for the BFS portion.
  • Backtracking Complexity: The backtracking (DFS) part is used to find all shortest paths from start to end, which has a time complexity of , where α represents the number of such paths.
  • Overall Time Complexity: The overall time complexity of the algorithm is , accounting for both the BFS construction of the adjacency list and distances, as well as the DFS to enumerate all shortest paths.

Space Complexity:

  • Storage of wordList: Copying the wordList into a set or similar data structure for efficient lookups requires space, where N is the number of words, and K is the maximum length of a word.

  • Adjacency List: The BFS algorithm constructs an adjacency list to represent the graph, which requires additional space. However, the space required for storing the adjacency list and distances map is dominated by the space needed to store the words themselves, contributing to the overall space complexity of .

  • Overall Space Complexity: Hence, the total space complexity of the algorithm is , dominated by the storage of the wordList and the auxiliary data structures (adjacency list, distances map, and the recursion stack during DFS).

Word Ladder II (hard)
Number of Flowers in Full Bloom (hard)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity:

Space Complexity: